% \begin{itemize}
% \item given assignment, compute the maximum delay.
% \item the iterative equation + proofs
% \item Explain how an exhaustive enumeration of all request-to-bus-slot assignment can solve the problem
% \end{itemize}
In this section, we first describe a method to compute the maximum waiting time, given a single request, a free bus slot and the bus availability model. The same rationale is then extended to compute the cumulative
waiting time for a sequence of requests of a given task in conformance to certain constraints. For a given request-to-slot assignment (i.e. when request k of task $\tau_i$ is assigned to slot $\Assignment{i}{k}$), the key idea is to release the request as early as possible and delay the servicing of the request to the latest possible time of the given slot to maximize the delay.
In other words, for the given slot we need to determine the \emph{lower} bound on the release time of a request, an \emph{upper} bound on the service time of a request for the given slot and
then compute the resulting waiting time. A set of lemmas are provided below as foundations to this central theme. 

\begin{Property}
By construction, $\Tmax{i}{1}$ is the longest waiting time for one request before it can be assigned a free bus slot.
This is because the underlying algorithm to compute this value (see~\cite{Icess12} for details) considers the ordering of tasks in a core in a manner in which they issue the maximum memory requests in a given time interval.
\end{Property}

% 
% \begin{figure}[!ht]
% \centering
% \includegraphics*[width=1\linewidth, viewport = 0 0 720 450]{../figures/lemma1.pdf}
% \caption{Visualization of the reasoning used in the proof of Lemma~\ref{lem:releaseLB}}.
% \label{fig:lemma1}
% \end{figure}
\subsection{Maximum Delay for a Single Request-to-Slot Assignment}
\label{sec:maxdelay_single}

We now proceed in Lemmas~\ref{lem:releaseLB} and~\ref{lem:UBreqserv} by lower bounding the release time
of a request and upper bounding the service time to enable the computation of its maximum delay.

\begin{lemma}[Lower bound on the release time of a request]
\label{lem:releaseLB}
For any task $\tau_i \in \tau$ and for all $k > 1$, let $\request{i}{k-1}$ and $\request{i}{k}$ be two consecutive requests generated by $\tau_i$. For a given request-to-slot assignment $\Assignment{i}{k-1}$ and $\Assignment{i}{k}$, if request $\request{i}{k-1}$ has been served at time $\reqserv{i}{k-1}$ in the $\Assignment{i}{k-1}$'th free bus slot then it holds that
\begin{equation}
\label{equ:LBreqrel}
\reqrel{i}{k} \geq \max(\Tmin{i}{\Assignment{i}{k} - 1} + 1, \reqserv{i}{k-1} + \Assignment{i}{k} - \Assignment{i}{k-1})
\end{equation}
\end{lemma}
\begin{proof}
The lemma is based on two simple observations: (i) The earliest time at which a request can be released is just after the earliest time of the release of the previous request. i.e. $\reqrel{i}{k} \geq \Tmin{i}{\Assignment{i}{k} - 1} + 1$, and more importantly, (ii) A request can only be released after the previous request is served i.e. $\reqrel{i}{k} \geq \reqserv{i}{k-1}$ . In addition, for it to be served in slot  $\Assignment{i}{k}$, all the intermediate slots between the slot occupied by the previous request must be occupied, since it is a work-conserving bus. This gets us to the term $\reqrel{i}{k} \geq  \reqserv{i}{k-1} + \Assignment{i}{k} - \Assignment{i}{k-1}$. In order to satisfy both conditions, the maximum of the resulting values is considered. 
% First, given that $\request{i}{k}$ is served when the bus is free for the $\Assignment{i}{k}$'th time, it immediately follows that $\request{i}{k}$ must have been released \emph{after} the bus was free for the $(\Assignment{i}{k} - 1)$'th time; Otherwise $\request{i}{k}$ would have been served in that $(\Assignment{i}{k} - 1)$'th free slot instead of the $\Assignment{i}{k}$'th. Since the \emph{earliest} time-instant at which the bus can be free for the $(\Assignment{i}{k} - 1)$'th time is $\Tmin{i}{\Assignment{i}{k} - 1}$ and since $\request{i}{k}$ must have been released afterwards, the earliest time-instant at which it can have been released is $\Tmin{i}{\Assignment{i}{k} - 1} + 1$, which gives the left-hand side of the max operator of Inequality~\eqref{equ:LBreqrel}. 
% %Figure~\ref{fig:lemma1} gives a visualization of the demonstration.
% 
% Second, given that request $\request{i}{k-1}$ has been served in the $\Assignment{i}{k-1}$'th free slot at time $\reqserv{i}{k-1}$, the \emph{earliest} time-instant at which the bus can be available to $\tau_i$ for the $\Assignment{i}{k}$'th time is given by $\reqserv{i}{k-1} + \Assignment{i}{k} - \Assignment{i}{k-1}$; This lower-bound is obtained by assuming that all the bus slots are available to $\tau_i$ from time $\reqserv{i}{k-1}$ onward. Under this scenario, if request $\request{i}{k}$ was released before time-instant $\reqserv{i}{k-1} + \Assignment{i}{k} - \Assignment{i}{k-1}$ then instead of being served in the $\Assignment{i}{k}$'th free bus slot as assumed, $\request{i}{k}$ would have been served earlier, in one of those free bus slots between the $\Assignment{i}{k-1}$'th and the $\Assignment{i}{k}$'th. This gives the right-hand term of Inequality~\eqref{equ:LBreqrel}.
\end{proof}
\begin{lemma}[Upper bound on the service time of a request]
\label{lem:UBreqserv}
For any task $\tau_i \in \tau$ and for all $k > 1$, if request $\request{i}{k}$ is served at time $\reqserv{i}{k}$ in the $\Assignment{i}{k}$'th free bus slot then it holds that
\begin{equation}
\label{equ:UBreqserv}
\reqserv{i}{k} \leq \min(\Tmax{i}{\Assignment{i}{k}}, \reqrel{i}{k} + \Tmax{i}{1})
\end{equation}
\end{lemma}
\begin{proof}
The latest time at which a request $\request{i}{k}$ assigned to slot $\Assignment{i}{k}$ is served is $\Tmax{i}{\Assignment{i}{k}}$ (by definition). Since $\Tmax{i}{1}$ denotes the maximum delay that a request may suffer, the value of $\reqserv{i}{k}$ should not be greater than $\reqrel{i}{k} + \Tmax{i}{1}$. Equation~\eqref{equ:UBreqserv} upholds these two conditions by considering the minimum of the respective values.
\end{proof}
The maximum delay for servicing the given request $k$ in slot $\Assignment{i}{k}$  is then given by $\reqserv{i}{k} - \reqrel{i}{k}$.

\subsection{Maximum Cumulative Delay for a Request-to-Slot Mapping}

In the previous section, we established a method to compute an upper bound on the delay of a single request and a given slot assignment for that request. 
Now, we extend this result to maximize the cumulative delay of a \emph{sequence} of requests, given a request-to-sot mapping $A = \{ \AssignmentOne{i}{1}, \ldots, \AssignmentOne{i}{\NbReqPerTask{i}} \}$. 
To maximize the cumulative delay for the mapping $A$, we compute the individual maximum delay for each request by applying the lemmas described in Section~\ref{sec:maxdelay_single}. Since the release time (and thus the delay) of a given request $\request{i}{k}$ is dependent on the service time $\reqserv{i}{k-1}$ of the previous one (see Equation~\eqref{equ:LBreqrel}), we start by computing the maximum delay of the first request $\request{i}{1}$ and iterate up to request $\request{i}{\NbReqPerTask{i}}$.
We show in Lemma~\ref{lem:wccd} that this iterative process leads to a worst-case delay.
 
% For any task $\tau_i$, given a request-to-free-bus-slot assignment $\Assignment{i}{k}$ for each of the $\NbReqPerTask{i}$ requests $\request{i}{k}$ that $\tau_i$ can generate, the cumulative waiting time $\DelayOne{i}{x} = \sum_{k=1}^{\NbReqPerTask{i}} \reqserv{i}{k} - \reqrel{i}{k}$ of all these requests is maximized for:
\begin{lemma}[Worst-case cumulative delay]
\label{lem:wccd} 
Let $A = \{ \AssignmentOne{i}{1}, \ldots, \AssignmentOne{i}{\NbReqPerTask{i}} \}$ refer to a request-to-slot mapping for the $\NbReqPerTask{i}$ requests of task $\tau_i$. Let $\DelayOne{i}{\NbReqPerTask{i}}$ be the maximum cumulative delay for these $\NbReqPerTask{i}$ requests considering this mapping $A$ and $\Delta_k = \Assignment{i}{k} - \Assignment{i}{k-1}$ . Then $\DelayOne{i}{\NbReqPerTask{i}} = \sum_{k=1}^{\NbReqPerTask{i}} \reqserv{i}{k} - \reqrel{i}{k}$ of all these requests is maximized for:
% For any task $\tau_i$, given a request-to-free-bus-slot assignment $\Assignment{i}{k}$ for each of the $\NbReqPerTask{i}$ requests $\request{i}{k}$ that $\tau_i$ can generate, the cumulative waiting time $\DelayOne{i}{}, \NbReqPerTask{i}} = \sum_{k=1}^{\NbReqPerTask{i}} \reqserv{i}{k} - \reqrel{i}{k}$ of all these requests is maximized for:
\begin{small}
\newcommand{\WidestPart}{\ensuremath{\max( \Tmin{i}{\Assignment{i}{k} - 1} + 1, \reqserv{i}{k-1} + \Delta_k)}}%
\newcommand{\FixedSize}[1]{\makebox[\widthof{\WidestPart}][l]{\ensuremath{#1}}}%
\begin{align}
\reqrel{i}{k} &= 
   \begin{cases}
   \FixedSize{\Tmin{i}{\Assignment{i}{k} - 1} + 1}  \qquad \mbox{ if } k = 1\\
   \FixedSize{\max( \Tmin{i}{\Assignment{i}{k} - 1} + 1, \reqserv{i}{k-1} + \Delta_k)}   \label{equ:reqrelk}  \qquad \mbox{ otherwise}
   \end{cases} \\
	\reqserv{i}{k} &=\FixedSize{\min( \Tmax{i}{\Assignment{i}{k}}, \reqrel{i}{k} + \Tmax{i}{1} )}   \label{equ:reqservk}  
\end{align}
\end{small}
\end{lemma}
Due to the space limitations, please refer to the appendix for the proof.

With Lemma~\ref{lem:wccd}, we established that the summation of the individual maximum request-to-slot assignments leads to the cumulative delays for a particular set of slot assignments.
Next, we formulate a method to \emph{select} such a set amongst the available candidate sets.
While an obvious brute-force is available, it is computationally expensive and hence the next section proposes a more efficient method.
